package com.example.lcode.backtrack;

import java.util.ArrayList;
import java.util.List;

public class Question216 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> subRes = new ArrayList<>();
        combinationSum3(k, n, result, subRes, 0, 1);
        return result;
    }

    private void combinationSum3(int count, int target, List<List<Integer>> result, List<Integer> subRes,
                                 Integer currentCalc, Integer beginNum) {
        if (currentCalc == target && subRes.size() == count) {
            result.add(new ArrayList<>(subRes));
            return;
        } else if (subRes.size() > count || currentCalc >= target && subRes.size() < count) {
            return;
        }
        for (int i = beginNum; i <= 9 ; i++) {
            subRes.add(i);
            combinationSum3(count, target, result, subRes, currentCalc + i, i + 1);
            subRes.remove(subRes.size() - 1);
        }
    }

    public static void main(String[] args) {
        Question216 question216 = new Question216();
        List<List<Integer>> lists = question216.combinationSum3(3, 9);
        System.out.println(lists);
    }

}
